# -*-coding = utf-8 -*-

# @Time: 2021/4/13 16:40
# @Author: bistro
# @File: p783.py
# @Software: PyCharm
# 783.二叉搜索树节点最小距离
import sys


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    # 开一个数组存储节点值然后排序
    # def minDiffInBST(self, root: TreeNode) -> int:
    #     nums = []
    #     min_value = sys.maxsize
    #     res = self.traverse(root, nums)
    #     nums.sort(reverse=True)
    #     for i in range(len(nums)-1):
    #         if nums[i] - nums[i+1] < min_value:
    #             min_value = nums[i] - nums[i+1]
    #     return min_value
    #
    # def traverse(self, node: TreeNode, nums):
    #     nums.append(node.val)
    #     if node.left is None and node.right is None:
    #         return 0
    #     if node.left:
    #         self.traverse(node.left, nums)
    #
    #     if node.right:
    #         self.traverse(node.right, nums)
    temp = None
    ans = sys.maxsize

    def minDiffInBST(self, root: TreeNode) -> int:
        self.traverse(root)
        return self.ans

    def traverse(self, node: TreeNode):
        if node is None:
            return 0
        self.traverse(node.left)
        if self.temp is not None:
            self.ans = min(node.val - self.temp.val, self.ans)
        self.temp = node
        self.traverse(node.right)


"""
时间复杂度：O(n)，其中 n 为二叉搜索树节点的个数。每个节点在中序遍历中都会被访问一次且只会被访问一次，因此总时间复杂度为 O(n)。
空间复杂度：O(n)。递归函数的空间复杂度取决于递归的栈深度，而栈深度在二叉搜索树为一条链的情况下会达到 O(n) 级别。
递归之所以效率低下，就是需要反复的出入栈，底层就需要开辟栈空间，所以即使不在代码中开辟额外的空间，也容易达到O(n)复杂度
"""
